package com.cat.graphTheory;
import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/grid-teleportation-traversal/description/
 * @create 2025/9/22 21:03
 * @since JDK17
 */

public class Solution22 {
    public int minMoves(String[] matrix) {
        int n = matrix.length, m = matrix[0].length();
        if (matrix[n - 1].charAt(m - 1) == '#') {
            return -1;
        }
        int[] d = new int[]{-1, 0, 1, 0, -1};
        int[][] dis = new int[n][m];
        Deque<int[]> q = new ArrayDeque<>();
        Map<Character, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
            for (int j = 0; j < matrix[i].length(); j++) {
                if (Character.isUpperCase(matrix[i].charAt(j))) {
                    map.computeIfAbsent(matrix[i].charAt(j), k -> new ArrayList<>()).add(new int[]{i, j});
                }
            }
        }
        q.add(new int[]{0, 0});
        dis[0][0] = 0;
        while (!q.isEmpty()) {
            var p = q.pollFirst();
            char c = matrix[p[0]].charAt(p[1]);
            int dist = dis[p[0]][p[1]];
            if (p[0] == n - 1 && p[1] == m - 1) {
                return dist;
            }
            if (c != '.') { // 使用传送门
                var list = map.get(c);
                for (int i = 0; i < list.size(); i++) {
                    int nx = list.get(i)[0], ny = list.get(i)[1];
                    if (dis[nx][ny] > dist) {
                        dis[nx][ny] = dist;
                        q.addFirst(new int[] {nx, ny});
                    }
                }
                map.get(c).clear();
            }

            for (int i = 0; i < 4; i++) {
                int nx = p[0] + d[i], ny = p[1] + d[i + 1];
                if (nx == -1 || nx == n || ny == -1 || ny == m || matrix[nx].charAt(ny) == '#') {
                    continue;
                }
                if (dis[nx][ny] > dist + 1) {
                    dis[nx][ny] =  dist + 1;
                    q.addLast(new int[]{nx, ny});
                }
            }
        }
        return dis[n - 1][m - 1] == Integer.MAX_VALUE ? -1 : dis[n - 1][m - 1];
    }
}
